package LimitedTimeGame.Day_0203;

/**
 * @author zxc
 * @date 2023/02/03 15:07
 **/

import java.util.Arrays;

/**
 * 题目 ：K个逆序对数组
 * 题目详述 ：
 * 给出两个整数n和k，找出所有包含从1到n的数字，且恰好拥有k个逆序对的不同的数组的个数。
 * 逆序对的定义如下：对于数组的第i个和第j个元素，如果满i < j且 a[i]>a[j]，则其为一个逆序对；否则不是。
 * 由于答案可能很大，只需要返回 答案 mod 109+ 7 的值。
 *
 * 说明:
 *  n 的范围是 [1, 1000] 并且 k 的范围是 [0, 1000]。
 *
 */
public class KInversePairs {
    /**
     * 思路 ：
     * 假设f(i,j)为 i个元素中 && 同时拥有j个逆序对的数组个数;
     * ===>
     * 状态转移方程 ：
     * （1）一般情况 ：
     * f(i,j) = sum[f(i-1,j-k)],
     * （k的取值范围为[0,j - i + 1];）
     * （2）特殊情况 ：
     * f(1,0) = 1;
     * f(1,j) = 0;
     * f(i,0) = 1;
     * ===》 即，若是数组中有且仅有一个元素的话，则其逆序对个数 == 0;
     * @param n
     * @param k
     * @return
     */
    public int kInversePairs(int n, int k) {
        final int MOD = 1000000007;
        int[] dp = new int[k + 1];
        dp[0] = 1;
        for(int i = 2 ; i <= n ; i++){
            for(int j = k ; j >= 1 ; j--){
                dp[j] = Sum(dp, j >= i - 1 ? j - i + 1 : 0  , j);
                if(dp[j] >= MOD){
                    dp[j] -= MOD;
                }
                else {
                    dp[j] += MOD;
                }
            }
        }
        return dp[k];
    }

    private int Sum(int[] dp, int i , int j) {
        int sum = 0;
        for(int k = i ; k <= j ; k++){
            sum += dp[k];
        }
        return sum;
    }
}
